﻿/*
Fib数的2幂次模 
Time Limit:200MS  Memory Limit:32768K


Description:
已知菲波那契(简写为Fib)函数对于正整数构成一个数列。
 f(0)=1,f(1)=1,f(n)=f(n-1)+f(n-2)。
 n>1） 2的幂次方有2，4，8，…，第n项Fib数对于2的幂次方的余数是多少，是你现在要关心的问题。 

Input:
输入数据有若干整数对，每对整数m,n表示2的m(1≤m≤32)次幂和第n(0<n<400000)项Fib数。 
Output:
对于每对整数m,n，输出第n项Fib数对于2的m次方的余数。 
Sample Input:
2 2
2 3
5 28
Sample Output:
2
3
21
*/
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main(int argc, char* argv[])
{
	vector<unsigned> vm, vn;
	unsigned m, n;
	unsigned k = 3;
	while (k-- && cin >> m >> n)
	{
		vm.push_back(m);
		vn.push_back(n);
	}

	unsigned max_n = *max_element(vn.begin(), vn.end());
	//cout<<max_n<<endl;
	vector<unsigned long> fibs;
	fibs.reserve(max_n + 1);
	fibs.push_back(1);
	fibs.push_back(1);
	{
		for (unsigned i = 2; i <= max_n; ++i)
		{
			fibs.push_back(fibs[i - 1] + fibs[i - 2]);
			//cout<<fibs[i]<<" ";
		}
	}


	for (unsigned i = 0, size = vm.size(); i < size; ++i)
	{
		m = vm[i];
		n = vn[i];
		//cout<<m<<", "<<n<<": "<<fibs[n]<<", "<<((1u << m)-1u)<<endl;
		if (32u == m)
			cout << fibs[n] << endl;
		else
			cout << (fibs[n] & ((1u << m) - 1u)) << endl;
	}
	return 0;
}
/*
#include <stdlib.h>
#include <stdio.h>

int main(int argc, char* argv[])
{
	unsigned m, n;
	while (EOF != scanf("%u%u", &m, &n))
	{
		unsigned fib1 = 1u, fib2 = 2u, fib;
		unsigned mod = (1u << m)-1u;
		
		if(1==n)
			fib=fib1;
		else if(2==n)
			fib=fib2;
		else{
			while (n > 2)
			{
				fib = (fib1+fib2);
				fib1 = fib2;
				fib2 = fib;
				--n;
			}
		}

		printf("%u\n", 32==m? fib : (fib&mod));
	}

	return EXIT_SUCCESS;
}
*/